package com.ly.algorithm.leetcode.linked;

/**
 * @Classname Problem143
 * @Description
 * 给定一个单链表 L：L0→L1→…→Ln-1.txt→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1.txt→L2→Ln-2→…
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 * 示例 1.txt:
 *
 * 给定链表 1.txt->2->3->4, 重新排列为 1.txt->4->2->3.
 * 示例 2:
 *
 * 给定链表 1.txt->2->3->4->5, 重新排列为 1.txt->5->2->4->3.
 *
 * @Date 2020/10/20 21:47
 * @Author 冷心影翼
 */
public class Problem143 {
	public static void main(String[] args) {
		ListNode listNode = new ListNode(1);
		listNode.next = new ListNode(2);
		listNode.next.next = new ListNode(3);
		listNode.next.next.next = new ListNode(4);
//		listNode.next.next.next.next = new ListNode(5);
		Solution143 solution143 = new Solution143();
		solution143.reorderList(listNode);
		System.out.println(listNode.next.val);
	}
}


class Solution143 {
	public void reorderList(ListNode head) {
		if(head == null)
			return;
		ListNode middle = middleNode(head);
		ListNode n2 = reveseNode(middle.next);
		middle.next = null;
		marge(head, n2);
	}

	public ListNode middleNode(ListNode head) {
		ListNode slow = head;
		ListNode fast = head;
		while (fast.next!=null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}
	// 1.txt->2->3

	public ListNode reveseNode(ListNode head) {
		ListNode cur = head;
		ListNode pre = null;
		while (cur!=null) {
			ListNode temp = cur.next;
			cur.next = pre;
			pre = cur;
			cur = temp;
		}
		return pre;
	}

	//1.txt->2
	//3->4->5
	public void marge(ListNode n1,ListNode n2) {
		ListNode cur1 ;
		ListNode cur2 ;
		while (n1!=null && n2!=null) {
			cur1 = n1.next;
			cur2 = n2.next;

			n1.next = n2;
			n1 = cur1;
			n2.next = n1;
			n2 = cur2;
		}
	}
}